package com.demo.排序算法.test;

import com.demo.堆.Heap;

import java.util.Arrays;

/**
 * @author cl
 */
public class Sort {

    public static void main(String[] args) {
        int[] arr = {456, 23, 43, 55, 3, 45, 29, 87, 67, 98, 444, 324, 2, 42, 54, 45, 213, 123, 98, 54, 34};
        System.out.println("原数组： " + $(arr));

        int[] 冒泡排序数组 = Arrays.copyOf(arr , arr.length);
        冒泡排序(冒泡排序数组);
        System.out.println("冒泡排序数组： " + $(冒泡排序数组));

        int[] 选择排序数组 = Arrays.copyOf(arr , arr.length);
        选择排序(选择排序数组);
        System.out.println("选择排序数组： " + $(选择排序数组));

        int[] 插入排序数组 = Arrays.copyOf(arr , arr.length);
        插入排序(插入排序数组);
        System.out.println("插入排序数组： " + $(插入排序数组));

        int[] 归并排序数组 = Arrays.copyOf(arr , arr.length);
        归并排序(归并排序数组);
        System.out.println("归并排序： " + $(归并排序数组));

        int[] 快速排序数组 = Arrays.copyOf(arr , arr.length);
        快速排序(快速排序数组);
        System.out.println("快速排序： " + $(快速排序数组));

        int[] 堆排序数组 = Arrays.copyOf(arr , arr.length);
        堆排序(堆排序数组);
        System.out.println("堆排序： " + $(堆排序数组));

        int[] 计数排序数组 = Arrays.copyOf(arr , arr.length);
        计数排序(计数排序数组);
        System.out.println("计数排序： " + $(计数排序数组));

        int[] 桶排序数组 = Arrays.copyOf(arr , arr.length);
        桶排序(桶排序数组);
        System.out.println("计数排序： " + $(桶排序数组));
    }

    private static void 冒泡排序(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j ++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
    }

    private static void 选择排序(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[index] > array[j]) {
                    index = j;
                }
            }
            swap(array, i, index);
        }
    }

    private static void 插入排序(int[] array) {
        // 牌堆还有多少张 每次接一张牌
        for (int i = 1 ; i < array.length ; i++) {
            // 手中牌数
            int j = i;
            // 接的那一张牌
            int curr = array[i];
            // 整理手中的牌
            for (; j > 0; j--) {
                if (array[j - 1] < curr) {
                    break;
                }
                // 挪动
                array[j] = array[j - 1];
            }
            // 将接的扑克插入它该插入的位置
            array[j] = curr;
        }
    }

    private static void 归并排序(int[] array) {
        归并排序0(array, 0, array.length - 1);
    }

    private static void 归并排序0(int[] array, int top, int tail) {
        if (top == tail) {
            return;
        }
        int mid = top + ((tail - top) >> 1);
        归并排序0(array, top, mid);
        归并排序0(array, mid + 1, tail);
        归并排序1(array, top, mid, tail);
    }

    private static void 归并排序1(int[] array, int top, int mid, int tail) {
        int[] tmp = new int[tail - top + 1];
        int i = top;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= tail) {
            if (array[i] < array[j]) {
                tmp[index++] = array[i++];
            } else {
                tmp[index++] = array[j++];
            }
        }
        while (i <= mid) {
            tmp[index++] = array[i++];
        }
        while (j <= tail) {
            tmp[index++] = array[j++];
        }
        for(i = top, index = 0; i <= tail;) {
            array[i++] = tmp[index++];
        }
    }

    private static void 快速排序(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int s, int e) {
        if (s == e) {
            return;
        }
        int mid = quickSortGet(arr, s, e);
        quickSort(arr, s, mid > s ? mid - 1 : s);
        quickSort(arr, mid < e ? mid + 1 : e, e);
    }

    // 找位置返回角标
    private static int quickSortGet(int[] arr, int s, int e) {
        // 排序1.0 取第一个元素，找它的位置
        // 排序3.0 随机取一个数放在第一个位置
        swap(arr, s + (int)(Math.random() * (e - s + 1)), s);
        int tmp = arr[s];

        int x = s;
        int d = e + 1;
        for (int i = s + 1; i < d;) {
            if (arr[i] < tmp) {
                swap(arr, ++x, i++);
            } else if (arr[i] > tmp) {
                swap(arr, --d, i);
            } else {
                i++;
            }
        }
        swap(arr, s, --d);
        return d;
    }

    private static void 堆排序(int[] arr) {
        // 先变成大根堆 n
        /*for (int i = 1; i < arr.length; i++) {
            Tree.heapInsert(arr, i);
        }*/

        for (int index = arr.length - 1; index > 0; index--) {
            Heap.heapify(arr, index, arr.length);
        }

        int heapSize = arr.length;
        while (heapSize > 0) {
            heapSize--;
            swap(arr, 0, heapSize);
            Heap.heapify(arr, 0, heapSize);
        }
    }

    private static void 计数排序(int[] arr) {
        // 申请一个数据区 min - max
        int[] tmp = new int[1000];
        int k = 0;
        // 放
        for (int i = 0; i < arr.length; i++) {
            tmp[arr[i]]++;
        }
        // 遍历
        for(int i = 0; i < tmp.length; i++) {
            for (int j = 0; j < tmp[i]; j++) {
                arr[k++] = i;
            }
        }
    }

    private static void 桶排序(int[] arr) {
        // 计算它的位数
        int w = getWeiShu(arr);

        // 按照位数进行进去出来
        for (int i = 0; i < w; i++) {

        }

    }

    private static int getWeiShu(int[] arr) {
        int w = 0;
        for (int a : arr) {
            if (w < String.valueOf(a).length()) {
                w =  String.valueOf(a).length();
            }
        }
        return w;
    }

    public static void swap(int[] array, int i, int j) {
        if (i < array.length && j < array.length && i != j) {
            array[i] = array[i] ^ array[j];
            array[j] = array[i] ^ array[j];
            array[i] = array[i] ^ array[j];
        }
    }

    private static String $(int[] array) {
        return Arrays.toString(array);
    }
}
